//剑指offer26
//输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
//要求不能创建任何新的结点，只能调整树中结点指针的指向。

//思路：创建一个顺序表存储二叉搜索树的中序遍历，再遍历这个顺序表，调整每个节点的left和right域。
import java.util.ArrayList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }
**/
class Solution{
	public TreeNode Convert(TreeNode pRootOfTree){
		if(pRootOfTree==null){
			return null;
		}
		ArrayList<TreeNode> list=new ArrayList<>();
		inOrderTraversal(pRootOfTree,list);
		return helper(list);
	}
	
	void inOrderTraversal(TreeNode root,ArrayList<TreeNode> list){//中序遍历
		if(root==null){
			return;
		}
		inOrderTraversal(root.left,list);
		list.add(root);
		inOrderTraversal(root.right,list);
	}
	
	public TreeNode helper(ArrayList<TreeNode> list){
		for(int i=0;i<list.size();i++){
			list.get(i).right=list.get(i+1);//调整节点
			list.get(i+1).left=list.get(i);
		}
		return list.get(0);//返回头结点
	}
}